package leetcode.leetcode17xx.leetcode1735;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

class SolutionTest {

    @Test
    void test1() {
        int[][] queries = {{2, 6}, {5, 1}, {73, 660}};
        int[] expected = {4, 1, 50734910};
        assertArrayEquals(expected, new Solution().waysToFillArray(queries));
    }

    @Test
    void test2() {
        int[][] queries = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
        int[] expected = {1, 2, 3, 10, 5};
        assertArrayEquals(expected, new Solution().waysToFillArray(queries));
    }

    @Test
    void test3() {
        int[][] queries = {{6454, 3435}, {738, 3186}, {4676, 3275}, {8823, 8234}, {2091, 1089}, {8408, 2942}, {4850, 1596}, {5979, 6143}, {1702, 3282}, {7899, 9150}, {1743, 4046}, {7573, 180}, {8739, 4930}, {6587, 550}, {5446, 8451}, {2657, 1189}, {9279, 3844}, {7753, 7128}, {5830, 9309}, {1989, 3984}, {6523, 7091}, {5928, 6504}, {524, 7207}, {6428, 8592}, {5355, 1746}, {8942, 3271}, {8706, 5624}, {9308, 7885}, {5498, 683}, {102, 4398}, {5524, 4742}, {8837, 266}, {534, 1025}, {3980, 5767}, {2315, 9676}, {3771, 1822}, {9066, 7051}, {6026, 9914}, {7089, 288}, {7341, 4214}, {2379, 6706}, {1688, 5232}, {685, 3183}, {5579, 545}, {2109, 8814}, {9865, 6325}, {3260, 8040}, {2642, 342}, {6265, 6542}, {1470, 6977}, {28, 700}, {5127, 5807}, {8562, 1595}, {6522, 5971}, {3062, 9464}, {1994, 8256}, {815, 9722}, {2013, 1627}, {9667, 3165}, {2953, 3430}, {6814, 4415}, {868, 4031}, {4501, 2637}, {4148, 8361}, {194, 7074}, {5235, 6375}, {3718, 5319}, {6214, 5862}, {4507, 4984}, {2865, 5567}, {9856, 4483}, {1538, 9623}, {4816, 4652}, {6080, 9568}, {4803, 6634}, {7956, 1386}, {4657, 6310}, {6672, 2348}, {6850, 6227}, {3360, 1536}, {3176, 7203}, {251, 4934}, {5567, 1405}, {2716, 3998}, {7649, 4676}, {4932, 1028}, {7447, 5754}, {1101, 912}, {5790, 2531}, {3081, 4776}, {6312, 6771}, {845, 5185}, {9058, 1538}, {2091, 2232}, {2804, 8569}, {9421, 1380}, {1302, 5492}, {661, 5249}, {3286, 2661}, {9970, 5047}, {858, 8067}, {2954, 7810}, {1768, 8310}, {2189, 9268}, {1964, 7821}, {302, 1618}, {735, 1366}, {5764, 4543}, {553, 7545}, {1720, 3010}, {9183, 8468}, {8700, 2230}, {804, 8910}, {2247, 7975}, {4955, 5004}, {5128, 6681}, {8177, 6590}, {5118, 2581}, {7597, 573}, {6402, 8796}, {3986, 9403}, {710, 2719}, {8084, 39}, {4195, 8806}, {9509, 7079}, {8258, 8377}, {3648, 1384}, {2217, 1466}, {8882, 4446}, {2045, 9127}, {2333, 3481}, {1882, 463}, {7959, 102}, {4749, 8620}, {1715, 3557}, {7503, 8160}, {7737, 8529}, {9459, 5361}, {8733, 3074}, {3178, 1171}, {2370, 9788}, {4336, 3486}, {6031, 857}, {7340, 8362}, {5799, 4758}, {7511, 2859}, {1923, 8942}, {6473, 229}, {312, 4272}, {4890, 7237}, {7530, 2734}, {1568, 7388}, {6019, 1104}, {5464, 498}, {9666, 1417}, {927, 7832}, {952, 8473}, {3923, 6499}, {8977, 2338}, {8978, 6303}, {7501, 6217}, {5107, 6}, {5562, 542}, {7513, 5204}, {2207, 13}, {6782, 543}, {5366, 1207}, {8386, 5674}, {1580, 9844}, {712, 7643}, {6794, 9897}, {9480, 8008}, {4362, 7683}, {1812, 6946}, {8205, 1812}, {8510, 3888}, {7032, 497}, {7284, 5186}, {6582, 8296}, {2417, 311}, {7831, 9701}, {2528, 3804}, {4021, 3631}, {8942, 1206}, {5752, 8850}, {3513, 8945}, {284, 6828}, {3965, 7498}, {4377, 2431}, {5399, 9942}, {3232, 8324}, {1860, 6637}, {9753, 1474}, {5693, 5098}, {4051, 3516}, {6807, 2231}, {7488, 2261}, {868, 7556}, {3240, 803}, {2268, 596}, {4349, 4748}, {2305, 7595}, {5298, 8133}, {9174, 7895}, {4382, 5957}, {4354, 4278}, {2640, 5503}, {5912, 779}, {2141, 4425}, {3775, 2409}, {7584, 9531}, {5800, 9996}, {5996, 1968}, {9773, 3176}, {6360, 7694}, {588, 2307}, {3489, 2533}, {2067, 792}, {6791, 6938}, {9522, 8213}, {4575, 5680}, {3429, 6167}, {5309, 9830}, {3436, 3912}, {4059, 8453}, {9394, 6798}, {8947, 5242}, {4221, 7848}, {7259, 1402}, {9434, 5676}, {3096, 9684}, {8587, 9540}, {5409, 9483}, {522, 9767}, {9431, 4498}, {9497, 6751}, {4635, 3296}, {64, 4582}, {3978, 6378}, {4421, 4423}, {4158, 7205}, {5323, 5785}, {5527, 6987}, {8147, 7539}, {9540, 7309}, {6257, 9487}, {9014, 1551}, {373, 1699}, {3476, 4439}, {9073, 6672}, {2929, 3613}, {2909, 5205}, {867, 8345}, {3497, 8165}, {9814, 3321}, {498, 2230}, {8414, 9836}, {6425, 9756}, {1631, 6937}, {2424, 7791}, {7870, 3748}, {9205, 6522}, {8419, 5943}, {7646, 2353}, {4755, 4872}, {7116, 7915}, {9262, 3993}, {6189, 6672}, {8888, 2627}, {7972, 9321}, {7275, 3282}, {3626, 5458}, {5489, 3288}, {4424, 9118}, {5791, 7183}, {1977, 118}, {4437, 2733}, {8377, 4725}, {8478, 3792}, {810, 296}, {7684, 5786}, {4292, 9533}, {3338, 9334}, {8882, 1736}, {1920, 3927}, {2634, 4207}, {8553, 2218}, {2530, 115}, {3777, 9379}, {6000, 3724}, {8439, 4225}, {8809, 2256}, {444, 6628}, {8581, 9638}, {9583, 2463}, {8071, 9832}, {7919, 415}, {2843, 9021}, {3675, 3938}, {2868, 5084}, {4661, 3684}, {5443, 2862}, {9990, 2238}, {4502, 831}, {6131, 9107}, {8288, 9439}, {7896, 7288}, {9466, 9656}, {5284, 2200}, {2518, 4312}, {5090, 5571}, {4463, 1970}, {2317, 487}, {3758, 4029}, {7887, 211}, {4037, 7074}, {4160, 1553}, {5453, 7265}, {5567, 7261}, {9041, 6676}, {613, 4120}, {602, 1621}, {2757, 172}, {6123, 5550}, {8635, 9838}, {892, 871}, {2666, 667}, {9603, 254}, {8502, 6244}, {1758, 4094}, {4165, 3072}, {4779, 3147}, {7604, 885}, {155, 4464}, {4263, 5358}, {8531, 2184}, {6042, 1772}, {5253, 4535}, {5633, 513}, {8029, 7408}, {7883, 625}, {1925, 6510}, {7953, 5832}, {8809, 4011}, {8628, 3231}, {272, 6398}, {8902, 4342}, {5408, 9242}, {8806, 2127}, {7628, 9982}, {9582, 7148}, {3146, 3357}, {1024, 3935}, {7378, 7862}, {9970, 1584}, {7635, 6364}, {4388, 6582}, {3233, 715}, {4086, 3189}, {1863, 4688}, {3659, 7596}, {4822, 1268}, {1332, 2794}, {7620, 4419}, {3659, 7798}, {1484, 1954}, {1459, 6482}, {487, 3361}, {1471, 7667}, {7086, 83}, {2585, 3985}, {7110, 8837}, {5511, 4142}, {36, 1952}, {1938, 2425}, {8127, 6625}, {3896, 1699}, {3741, 3451}, {8175, 9069}, {3066, 7564}, {2236, 5269}, {1562, 1650}, {9277, 359}, {3290, 9943}, {9665, 2023}, {4515, 5929}, {9136, 3398}, {366, 7822}, {9775, 1488}, {3767, 928}, {4802, 3262}, {8463, 6188}, {1730, 5606}, {9221, 7036}, {9005, 4863}, {5245, 7489}, {1870, 4177}, {673, 7477}, {3899, 5423}, {2814, 218}, {8755, 1875}, {4366, 5049}, {2539, 12}, {2130, 3386}, {4917, 2997}, {5333, 5969}, {5931, 2329}, {1820, 6136}, {1758, 5911}, {5489, 6967}, {6639, 5734}, {6246, 1844}, {8283, 871}, {5412, 1280}, {9235, 7264}, {8181, 6540}, {7861, 1035}, {7333, 3844}, {7091, 5121}, {8502, 3032}, {9943, 3352}, {8213, 991}, {5912, 6532}, {5368, 1695}, {5245, 1870}, {9072, 9183}, {9149, 9957}, {8693, 5978}, {23, 8438}, {6288, 4299}, {7029, 8118}, {5691, 3043}, {9963, 3637}, {7644, 8887}, {3787, 8681}, {2986, 7110}, {5212, 5875}, {2816, 4893}, {9764, 518}, {348, 6915}, {1286, 8932}, {2832, 3989}, {6487, 477}, {8554, 7468}, {7451, 8826}, {7486, 4639}, {4045, 5608}, {2048, 5609}, {9658, 5218}, {5163, 5788}, {377, 6648}, {6354, 821}, {5440, 7940}, {804, 1824}, {5996, 9095}, {2971, 5380}, {8666, 4593}, {9630, 1367}, {6260, 9611}, {2534, 8398}, {2705, 3071}, {8588, 2241}, {9546, 4851}, {1835, 6174}, {4250, 6603}, {7623, 4536}, {900, 657}, {2005, 4095}, {1063, 4301}, {486, 1483}, {515, 3370}, {2731, 7456}, {4523, 7076}, {9483, 4535}, {4457, 7563}, {7752, 6631}, {625, 6055}, {9989, 8317}, {8641, 5086}, {1945, 4147}, {2322, 7901}, {6344, 6319}, {2180, 923}, {3394, 5834}, {2457, 887}, {2541, 8245}, {8422, 928}, {6528, 4464}, {3692, 9885}, {4247, 4283}, {4618, 9525}, {5955, 4487}, {5839, 787}, {1445, 1266}, {2068, 5329}, {1653, 3877}, {2644, 6475}, {5166, 915}, {9607, 4145}, {7434, 5153}, {8241, 4170}, {6024, 7336}, {6710, 2186}, {7913, 5921}, {8177, 9024}, {1361, 4810}, {4219, 3748}, {9963, 7740}, {1915, 641}, {5883, 7860}, {7003, 5294}, {7955, 9831}, {8917, 599}, {9830, 8643}, {6541, 1361}, {8234, 8004}, {159, 411}, {1962, 5333}, {5052, 5977}, {4062, 2230}, {5295, 1720}, {3632, 8821}, {8011, 9083}, {8184, 6546}, {4838, 5733}, {5034, 2795}, {9773, 6392}, {1419, 3220}, {6955, 4022}, {5577, 509}, {9675, 2077}, {5809, 699}, {4643, 7220}, {7938, 3685}, {246, 7282}, {9533, 7250}, {5692, 4433}, {4426, 1904}, {9008, 4138}, {3547, 629}, {191, 2419}, {2396, 7763}, {7831, 7292}, {1744, 8586}, {4953, 2033}, {4637, 2185}, {3733, 743}, {2113, 3163}, {3644, 7030}, {4843, 1221}, {5009, 3290}, {1314, 6915}, {8861, 4238}, {4081, 4515}, {1318, 4844}, {3607, 2501}, {6461, 5597}, {6233, 7107}, {5982, 5453}, {3599, 3562}, {7118, 8234}, {7969, 1092}, {6252, 9972}, {3974, 7372}, {1860, 8731}, {561, 7278}, {9832, 355}, {4883, 6408}, {5116, 1690}, {621, 7791}, {3191, 1948}, {4719, 5963}, {7650, 1467}, {7308, 7720}, {7662, 1998}, {7402, 2747}, {6451, 8177}, {3811, 5391}, {3269, 7467}, {3538, 8939}, {5311, 1926}, {976, 3100}, {1629, 1209}, {1180, 8919}, {7780, 8124}, {7832, 5772}, {8957, 4521}, {5808, 2532}, {8336, 8673}, {94, 4607}, {3706, 7766}, {2352, 2462}, {8540, 2605}, {5569, 7688}, {5129, 2102}, {6434, 2868}, {6190, 8256}, {9164, 4419}, {9864, 2266}, {1929, 6449}, {3016, 7028}, {2010, 627}, {9020, 2951}, {387, 4552}, {683, 9071}, {2566, 7459}, {3427, 1426}, {7281, 9517}, {6875, 7773}, {4368, 7646}, {665, 2689}, {8223, 9064}, {2213, 4069}, {285, 7933}, {435, 985}, {4835, 6797}, {5181, 4308}, {8427, 8973}, {2566, 4362}, {5659, 6536}, {7908, 7303}, {9477, 639}, {1500, 7310}, {1791, 3179}, {2743, 5362}, {832, 5074}, {1539, 1342}, {8119, 4481}, {5385, 6574}, {5188, 4436}, {5772, 8964}, {3812, 1063}, {4109, 842}, {5891, 230}, {2180, 5206}, {976, 8679}, {2114, 3992}, {1486, 4033}, {361, 9663}, {511, 9944}, {6263, 2305}, {6358, 2458}, {8088, 4601}, {1209, 7277}, {9247, 2474}, {9592, 9996}, {2359, 9500}, {3280, 4859}, {8789, 7220}, {5759, 1679}, {4056, 2085}, {5230, 5118}, {885, 1554}, {9955, 6005}, {6616, 7787}, {4716, 2332}, {5786, 7194}, {3717, 887}, {1561, 4015}, {3100, 6536}, {6410, 1295}, {5797, 1092}, {5915, 616}, {5137, 5731}, {5846, 7885}, {8992, 4048}, {5556, 3178}, {692, 8631}, {431, 2497}, {8150, 4287}, {9262, 2497}, {5516, 3152}, {1707, 5839}, {5111, 3673}, {7340, 4307}, {8800, 7}, {927, 8348}, {1869, 8046}, {6162, 7529}, {5897, 8795}, {3094, 5626}, {6702, 2822}, {4186, 6881}, {4670, 3208}, {1021, 7628}, {5616, 8100}, {8664, 605}, {9667, 8837}, {3360, 3289}, {2869, 2905}, {6634, 9852}, {7029, 2237}, {2530, 3843}, {5460, 5841}, {2915, 1415}, {9797, 6945}, {3358, 7108}, {5136, 6269}, {9868, 1610}, {2303, 2124}, {2459, 5030}, {3544, 1478}, {5329, 3445}, {4957, 1144}, {8886, 3311}, {5148, 8697}, {7483, 4691}, {4613, 4715}, {8782, 4548}, {9786, 8989}, {1219, 5179}, {2873, 2829}, {7518, 4528}, {139, 616}, {6021, 7188}, {2058, 4708}, {1444, 3588}, {6525, 3349}, {8793, 2745}, {5605, 9534}, {2143, 5207}, {6024, 2414}, {8020, 4786}, {4466, 6157}, {9400, 2620}, {3905, 6870}, {397, 5406}, {910, 9832}, {3846, 435}, {6885, 2836}, {9341, 4442}, {6462, 4096}, {6822, 3566}, {4354, 5641}, {4727, 4246}, {6254, 4548}, {4257, 2401}, {2306, 3434}, {3187, 6126}, {8708, 7333}, {6347, 9791}, {6303, 2189}, {9909, 7837}, {6485, 4217}, {3236, 4043}, {423, 736}, {5001, 3324}, {578, 7828}, {3408, 8885}, {1757, 6326}, {1900, 2099}, {8600, 1657}, {2598, 9789}, {9796, 8124}, {1218, 3092}, {9588, 7556}, {1113, 3217}, {5272, 6570}, {9062, 5727}, {4511, 5337}, {2759, 2198}, {1205, 9792}, {3091, 3793}, {8255, 4909}, {7235, 7311}, {3185, 9986}, {2324, 2990}, {6961, 7887}, {567, 8299}, {3249, 5918}, {5567, 8077}, {5903, 3137}, {1596, 3622}, {2187, 8244}, {8964, 7006}, {7282, 5614}, {6288, 6534}, {4544, 815}, {6306, 6944}, {4287, 6343}, {4791, 4969}, {6162, 6377}, {866, 9366}, {1805, 2243}, {1626, 1460}, {1933, 4090}, {7915, 2835}, {5853, 401}, {5449, 2825}, {6041, 5864}, {6882, 4035}, {3961, 191}, {973, 1679}, {4717, 3780}, {4533, 4332}, {7906, 1996}, {9876, 6709}, {9974, 6015}, {8694, 1500}, {6406, 2626}, {4740, 6139}, {9537, 6969}, {4001, 4529}, {2108, 3688}, {7761, 7153}, {5862, 7458}, {8530, 1462}, {5664, 3448}, {1989, 7706}, {5347, 5333}, {3121, 2905}, {738, 4665}, {9738, 5083}, {4072, 8005}, {2254, 5420}, {810, 7562}, {329, 653}, {7670, 5569}, {2970, 420}, {6485, 2198}, {4321, 2936}, {1347, 148}, {3574, 1753}, {8420, 95}, {4018, 6419}, {9400, 1265}, {2595, 9896}, {8390, 9967}, {4146, 2345}, {6101, 8246}, {4404, 9332}, {8899, 6558}, {5556, 4674}, {8117, 8154}, {7771, 2647}, {9792, 4555}, {9813, 2536}, {3388, 8740}, {2206, 8175}, {4265, 2599}, {6169, 3992}, {1439, 1332}, {2567, 7541}, {7998, 9966}, {1554, 236}, {1700, 4945}, {5330, 4753}, {3733, 7865}, {637, 4609}, {7237, 5696}, {8336, 2306}, {7861, 5897}, {6913, 3025}, {5577, 7368}, {9633, 1693}, {6555, 3462}, {5998, 775}, {3539, 8123}, {9049, 4214}, {5426, 973}, {2610, 2739}, {2471, 9864}, {2803, 6455}, {7395, 9030}, {4101, 7003}, {6257, 5161}, {5628, 1996}, {9008, 5143}, {5528, 8560}, {2716, 5094}, {8138, 5596}, {7672, 8897}, {7272, 7421}, {5039, 2057}, {7275, 817}, {9413, 3851}, {7009, 3592}, {7986, 4161}, {5158, 8144}, {155, 3569}, {4660, 1405}, {5392, 199}, {9728, 2525}, {5467, 930}, {2052, 3023}, {3057, 1620}, {3315, 9121}, {7363, 6959}, {9573, 7070}, {636, 5998}, {4597, 5221}, {4297, 7903}, {1297, 1924}, {7902, 901}, {8011, 4314}, {7535, 976}, {4944, 4223}, {6663, 6809}, {7217, 9898}, {5144, 7189}, {9716, 4210}, {9692, 1948}, {8493, 8079}, {5633, 6181}, {4713, 5764}, {8409, 4905}, {8276, 1999}, {3948, 2149}, {8958, 7382}, {7290, 2416}, {5027, 8291}, {5591, 2181}, {3009, 8352}, {3599, 335}, {3002, 1745}, {8855, 3183}, {4049, 4636}, {1622, 4747}, {7045, 2016}, {642, 5924}, {945, 603}, {9429, 9785}, {9187, 6392}, {2875, 1185}, {6789, 1475}, {2625, 9880}, {666, 4877}, {7061, 471}, {1756, 9379}, {2358, 304}, {7380, 8370}, {1052, 7196}, {400, 1664}, {9556, 1536}, {6803, 5579}, {7104, 6898}, {941, 5856}, {8644, 9980}, {7745, 1514}, {6621, 3867}, {8532, 3186}, {8395, 775}, {502, 2957}, {9998, 4574}, {5346, 6500}, {3471, 8845}, {3852, 7753}, {6124, 9610}, {4017, 3291}, {6341, 1597}, {503, 4506}, {5837, 7319}, {4895, 2448}, {8013, 3077}, {1917, 1025}, {8374, 7217}, {4288, 7472}, {1703, 4888}, {6351, 1184}, {7983, 4644}};
        int[] expected = {835662788, 813937882, 131246019, 829332965, 782565115, 70694464, 765035087, 5979, 930360380, 149730500, 518490585, 676011564, 340727876, 853595900, 319803593, 7059649, 123817735, 924857967, 155285614, 761649679, 42549529, 467323803, 524, 149883185, 982078619, 8942, 787523362, 434540470, 5498, 1061208, 30514576, 104027423, 76279230, 15840400, 849502688, 14220441, 82192356, 36312676, 258027169, 987239945, 464285848, 64783968, 469225, 31125241, 645251680, 447568839, 968825276, 565359502, 39250225, 1470, 4615408, 5127, 661755939, 42536484, 802264155, 466824378, 664225, 2013, 389737642, 159828842, 46430596, 753424, 603010936, 693647603, 509815758, 155918659, 4945602, 946126671, 35996480, 8208225, 9856, 1538, 862401791, 50850478, 799488857, 767786690, 999380693, 526244980, 46922500, 921300655, 254358302, 63001, 30991489, 7376656, 33235035, 996684683, 557551505, 595238043, 5790, 594751525, 478561571, 603351125, 82047364, 415638061, 46214310, 428551183, 104425399, 436921, 10797796, 563183485, 736164, 99912441, 775610586, 539529160, 154028379, 91204, 540225, 501382407, 169112377, 130498736, 865296661, 502995394, 227717173, 918413395, 920739274, 847856214, 741437411, 26193924, 57714409, 56660525, 3986, 710, 65351056, 481732795, 9509, 8258, 995991620, 4915089, 410074471, 2045, 2722611, 1882, 168271551, 477373271, 1715, 480638973, 59861169, 89472681, 24764175, 3178, 658834908, 687928505, 6031, 446901235, 345900718, 56415121, 111117418, 6473, 532243521, 4890, 56700900, 928790521, 119294293, 129336203, 93431556, 445918803, 906304, 15389929, 425265772, 667052291, 7501, 26081449, 30935844, 64498449, 2207, 45995524, 28793956, 70324996, 978614181, 712, 46158436, 215419011, 995965354, 949419293, 697793054, 237228488, 49449024, 53056656, 852334286, 2417, 61324561, 137875301, 4021, 421578943, 756360532, 12341169, 264148299, 334656691, 855130052, 376535100, 885674384, 1860, 715194288, 32410249, 151320117, 46335249, 853235339, 327362728, 10497600, 835668293, 137516888, 240487785, 28068804, 84162276, 142830380, 827408203, 2640, 34951744, 889482121, 796109004, 741805458, 214047237, 250359848, 433597150, 40449600, 345744, 12173121, 518890551, 46117681, 90668484, 534260113, 11758041, 636717586, 895320723, 16475481, 607126678, 80048809, 237125536, 52693081, 564563841, 207124492, 366260886, 252631823, 522, 828604125, 90193009, 299536705, 262144, 949796918, 4421, 887511815, 823632217, 837297007, 745788743, 9540, 39150049, 407289620, 373, 12082576, 915160081, 2929, 616775261, 751689, 764844179, 933891279, 123505992, 871626591, 268314040, 2660161, 493120717, 752668249, 958284672, 735019887, 58461316, 97490244, 50637456, 146394082, 555968905, 78996544, 642790506, 33919180, 13147876, 280179340, 585536422, 33535681, 3908529, 19686969, 959303669, 373816602, 10473696, 692986333, 4292, 192810213, 58511656, 544864877, 6937956, 73153809, 6400900, 14265729, 387463720, 845378615, 707198335, 43862760, 849582524, 91833889, 763859500, 62710561, 978970953, 633171532, 595011024, 724504259, 499395490, 2992021, 20268004, 37589161, 8288, 405698116, 954818217, 921897784, 218001606, 949068095, 895680231, 2317, 72595141, 7887, 469199849, 4160, 29735209, 30991489, 545095218, 850393723, 602, 481846501, 685687347, 74563225, 795664, 7107556, 92217609, 878147447, 433211477, 265610909, 22838841, 669481791, 842399919, 69190713, 309659463, 302165156, 27594009, 482956320, 322562293, 56080551, 848169059, 670511439, 565014348, 181663521, 20123648, 444361873, 29246464, 77545636, 259295871, 930246973, 573426621, 1048576, 54434884, 59132895, 562941846, 488938484, 792250106, 16695396, 699428589, 959068282, 71435574, 363266354, 254394653, 987719843, 2202256, 105745558, 487, 183010090, 7086, 6682225, 7110, 375246662, 23688288, 641290737, 627563719, 3896, 355597657, 66830625, 756899737, 4999696, 446133583, 9277, 10824100, 461280268, 373589355, 83466496, 133956, 244383790, 295803615, 730296838, 676465352, 2992900, 58761107, 81090025, 5245, 1870, 673, 273381286, 7918596, 40353290, 829268386, 187081614, 4536900, 49855443, 28440889, 35176761, 423600387, 3090564, 5489, 622693075, 855592879, 68608089, 205306121, 317344665, 160772124, 721888700, 64530775, 300967180, 836343056, 853996453, 8213, 517399627, 681194954, 470203018, 82301184, 83704201, 565868023, 529, 39538944, 599783895, 32387481, 9963, 7644, 3787, 252288701, 830458155, 330474342, 857729234, 42144192, 6067903, 2832, 511311284, 988591006, 660151960, 7486, 407687111, 4194304, 93276964, 827260682, 392519188, 6354, 72006203, 425869524, 568286431, 673019163, 75099556, 9630, 39187600, 244087719, 7317025, 175815807, 886360452, 485823132, 765624468, 517135137, 364905000, 690163301, 201157040, 486, 136590875, 51073209, 509629647, 89927289, 19864849, 60093504, 244140625, 9989, 74666881, 357983576, 2322, 40246336, 4752400, 11519236, 2457, 406426309, 411321502, 240727046, 325149538, 4247, 757193282, 35462025, 5839, 17196104, 2139346, 1653, 436492732, 867913337, 92294449, 7434, 365788307, 82214805, 45024100, 62615569, 684050483, 93063024, 557917451, 847813256, 1915, 146790542, 49042009, 408505354, 8917, 862080357, 6541, 632421431, 25281, 1962, 25522704, 22365859, 287722531, 3632, 64176121, 146769668, 76461886, 567378415, 544917291, 789361409, 48372025, 5577, 93605625, 33744481, 324038418, 188014172, 14886936, 55361889, 414332600, 392813295, 81144064, 12581209, 36481, 5740816, 146979196, 36409882, 24532209, 703702160, 3733, 2113, 828523428, 590864316, 160179977, 268747130, 741976516, 400161103, 944649841, 13010449, 41744521, 153849643, 61824670, 617130477, 640044512, 874722381, 325750531, 686794555, 1860, 176558481, 96668224, 32192053, 848794279, 479231453, 251239564, 22268961, 877822189, 310699155, 676685153, 54789604, 460949975, 682212037, 933713871, 12517444, 454948348, 784122763, 322781161, 822212200, 45931447, 115601967, 600838467, 13074947, 946465442, 8836, 899819466, 5531904, 72931600, 394596190, 26306641, 311117886, 838389459, 833288232, 752357831, 1929, 653473128, 120600944, 81360400, 767489097, 466489, 2566, 247815203, 53012961, 47265625, 19079424, 665, 647212445, 4897369, 285, 189225, 23377225, 442701579, 254380313, 895457384, 556685557, 62536464, 626310956, 499964566, 874082162, 638466267, 575930368, 645153798, 8119, 155440533, 831859525, 826021950, 3812, 16883881, 440561543, 360231930, 929714176, 379403109, 2208196, 130321, 155568969, 39225169, 40424164, 65415744, 1461681, 85507009, 535843688, 250700468, 10758400, 194425723, 33166081, 725807154, 55665999, 441396334, 99102025, 43771456, 831390391, 817172282, 3717, 803721460, 312669941, 374719159, 618652094, 251726068, 26388769, 791234343, 993244130, 508918419, 821051394, 185761, 66422500, 85784644, 321258108, 1707, 5111, 53875600, 8800, 398728656, 366429095, 6162, 34774609, 618354381, 32418301, 17522596, 283697546, 532687351, 452648952, 218659645, 9667, 933055741, 615200748, 87804932, 7029, 857400049, 129836871, 8497225, 327897993, 938317312, 5136, 638499242, 124959228, 868788481, 12559936, 334225232, 750844653, 647405549, 431800840, 7483, 163573711, 605662673, 95765796, 1219, 714112456, 116471720, 835686454, 872602275, 512232993, 798074407, 42575625, 472246020, 619891863, 4592449, 602380298, 64320400, 19945156, 64670880, 761822901, 840596713, 668662402, 888939344, 209302534, 87254281, 243587886, 46539684, 4354, 622587848, 753407548, 988766671, 262468532, 370259979, 8708, 6347, 39727809, 98188281, 6485, 10471696, 559999805, 610327817, 902609419, 11614464, 3087049, 1900, 8600, 535471073, 860427401, 904207878, 757154528, 1113, 333506931, 170021120, 907616661, 1731332, 795281886, 3091, 8255, 52345225, 10144225, 541548386, 298879322, 321489, 296447011, 30991489, 5903, 2547216, 198430419, 286940304, 146427066, 785647310, 20647936, 829060461, 4287, 4791, 37970244, 433998002, 1805, 189598397, 222633188, 299145467, 5853, 909612165, 31928456, 944758693, 3961, 946729, 846949254, 344737241, 112867397, 9876, 220255480, 914592765, 881969582, 22467600, 431811084, 16008001, 710037495, 60233121, 784680210, 650472660, 510616893, 3956121, 5347, 400540351, 401947272, 441328811, 16581184, 547064283, 531441000, 329, 7670, 392165642, 728132221, 639938054, 222911659, 3574, 70896400, 442018854, 583994190, 588372588, 8390, 266903639, 237585957, 717962946, 731391771, 550716175, 114747163, 7771, 95883264, 1660733, 101076236, 467267034, 18190225, 35648538, 471036623, 2567, 507100681, 877597183, 912999972, 723922425, 149293825, 405769, 728291468, 69488896, 7861, 918896206, 435129611, 9633, 655401908, 910023249, 3539, 26066439, 29441476, 779580881, 98641388, 7856809, 766715701, 16818201, 39150049, 147553145, 81144064, 449958534, 544179497, 510953675, 570725291, 52881984, 986632479, 52925625, 9413, 814979185, 316697693, 51687228, 24025, 21715600, 5392, 347011948, 857818842, 2052, 832649201, 10989225, 7363, 405756029, 404496, 21132409, 18464209, 4462465, 62441604, 114901733, 508000269, 24443136, 44395569, 187616305, 114025032, 196767277, 255315191, 72131049, 31730689, 10016400, 918409072, 8276, 15586704, 80245764, 473148416, 5027, 31259281, 355916881, 12952801, 9012004, 78411025, 381598278, 2630884, 875733637, 132510726, 422400825, 295054723, 620696206, 763671714, 477317703, 763634995, 666, 49857721, 3083536, 224350315, 340179307, 978993828, 566265055, 203958231, 46280809, 50466816, 124668231, 669553471, 59985025, 43837641, 269023756, 858350885, 502, 99960004, 896973354, 818055824, 3852, 436112438, 16136289, 6341, 127263527, 34070569, 616727285, 64208169, 524218530, 70123876, 437500850, 644230817, 42801985, 14419829};
        assertArrayEquals(expected, new Solution().waysToFillArray(queries));
    }


}